Max Divergence
Definition 2: Max Divergence
同一domainからとった確率変数$ Y, Zに対して、$ Yと$ ZのMax Divergence $ D_{\infty}(Y||Z)を以下で定義する
$ D_{\infty}(Y||Z) = \underset{S \sub Supp(Y)}{\mathrm{max}} \Bigl[ln \frac{\mathrm{Pr} [Y \in S]}{\mathrm{Pr}[Z \in S]} \Bigr]
Lemma7
$ D_{\infty}(Y||Z) \leq \epsilonかつ$ D_{\infty}(Z||Y) \leq \epsilonならば、$ D(Y||Z) \leq \epsilon(e^{\epsilon}-1)
The idea is that the expected privacy loss after k differentially private algorithms are run is bounded by the above lemma, and that with high probability, the total privacy loss is not much higher (By Azuma’s inequality).
cipepser.icon upper boundを確率的に抑えるという話？